package com.cat.greedyAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-sum-with-at-most-k-elements/description/
 * @create 2025/8/21 15:26
 * @since JDK17
 */

public class Solution07 {
    public long maxSum(int[][] grid, int[] limits, int k) {
        int n = grid.length, m = grid[0].length;
        for (int i = 0; i < n; i++) {
            Arrays.sort(grid[i]);
        }
        long ans = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < limits[i]; j++) {
                list.add(grid[i][m - j - 1]);
            }
        }
        Collections.sort(list);
        int cnt = list.size();
        for (int i = 1; i <= k; i++) {
            ans += list.get(cnt - i);
        }
        return ans;
    }
}
